package demo7;

import demo6.Solution;
import javafx.scene.chart.BubbleChart;

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Test {
    // //1.组合总和 III(回溯)
    // private List<List<Integer>> ret = new ArrayList<>();
    // private List<Integer> path = new ArrayList<>();
    // public List<List<Integer>> combinationSum3(int k, int n) {
    // dfs(k, n, 1);
    // return ret;
    // }
    //
    // private void dfs(int k, int n, int start) {
    // if(path.size() == k && n == 0) {
    // ret.add(new ArrayList<>(path));
    // return;
    // }
    // for(int i = start; i <= 9; i++) {
    // if(n < 0) {
    // continue;
    // }
    // path.add(i);
    // dfs(k, n - i, i + 1);
    // path.remove(path.size() - 0);
    // }
    // }
//
//    // 2.矩阵中的路径(回溯)
//    private int row;
//    private int col;
//    private int index;
//
//    public boolean exist(char[][] board, String word) {
//        this.row = board.length;
//        this.col = board[0].length;
//        for (int i = 0; i < row; i++) {
//            for (int j = 0; j < col; j++) {
//                boolean[][] path = new boolean[row][col];
//                index = 0;
//                if (board[i][j] == word.charAt(0)) {
//                    dfs(board, word, path, i, j);
//                    if (index >= word.length()) {
//                        return true;
//                    }
//                }
//            }
//        }
//        return false;
//    }
//
//    private void dfs(char[][] board, String word, boolean[][] path, int x, int y) {
//        if (index >= word.length()) {
//            return;
//        }
//        // 边界或者走过的情况
//        if (x < 0 || x >= row || y < 0 || y >= col || path[x][y]) {
//            return;
//        }
//        if (board[x][y] != word.charAt(index)) {
//            return;
//        }
//        index++;
//        path[x][y] = true;
//        dfs(board, word, path, x - 1, y);
//        dfs(board, word, path, x + 1, y);
//        dfs(board, word, path, x, y - 1);
//        dfs(board, word, path, x, y + 1);
//        if (index >= word.length()) {
//            return;
//        }
//        index--;
//        path[x][y] = false;
//    }

    // //3.所有可能的路径(回溯)
    // private List<List<Integer>> list = new ArrayList<>();
    // private List<Integer> path = new ArrayList<>();
    // public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    // int target = graph.length - 1;
    // path.add(0);
    // dfs(graph, target, 0);
    // return list;
    // }
    // private void dfs(int[][] graph, int target, int x) {
    // if(path.get(path.size() - 1) == target) {
    // list.add(new ArrayList<>(path));
    // return;
    // }
    // for(int i = 0; i < graph[x].length; i++) {
    // path.add(graph[x][i]);
    // dfs(graph, target, graph[x][i]);
    // path.remove(path.size() - 1);
    // }
    // }

    // //4 剑指 Offer 38. 字符串的排列(回溯)
    // private Set<String> list = new HashSet<>();
    // private int len;

    // public String[] permutation(String s) {
    // this.len = s.length();
    // String path = new String();
    // boolean[] flag = new boolean[len];
    // dfs(s, flag, path);
    // return list.toArray(new String[0]);
    // }

    // private void dfs(String s, boolean[] flag, String path) {
    // if (path.length() == len) {
    // list.add(path);
    // return;
    // }
    // for (int i = 0; i < len; i++) {
    // if (flag[i]) {
    // continue;
    // }
    // flag[i] = true;
    // dfs(s, flag, path + s.charAt(i));
    // flag[i] = false;
    // }
    // }

    // private boolean ret;
    // public boolean canPartitionKSubsets(int[] nums, int k) {
    // //先求出数组的和，进行特判
    // int sum = 0;
    // for(int i = 0; i < nums.length; i++) {
    // sum += nums[i];
    // }
    // if(sum % k != 0) {
    // return false;
    // }
    // //sum / k 就是每组需要求得的和
    // int arrSum = sum / k;
    // dfs(nums, arrSum, k, 0);
    // return ret;
    // }

    // private void dfs(int[] nums, int arrSum, int k, int sum) {
    // if(ret) {//特判
    // return;
    // }
    // if(sum == arrSum) {
    // k--;
    // if(k == 0) {
    // ret = true;
    // }
    // return;
    // }
    // for(int i = 0; i < )
    // }

    // //5. 字母大小写全排列(回溯)
    // private List<String> ret = new ArrayList<>();
    // private int ans = 'A' - 'a';

    // public List<String> letterCasePermutation(String s) {
    // char[] str = s.toCharArray();
    // dfs(str, 0);
    // return ret;
    // }

    // private void dfs(char[] str, int begin) {
    // ret.add(new String(str));
    // for (int i = begin; i < str.length; i++) {
    // if (str[i] >= '0' && str[i] <= '9') {
    // continue;
    // } else if (str[i] >= 'a' && str[i] <= 'z') {
    // str[i] += ans;
    // dfs(str, i + 1);
    // str[i] -= ans;
    // } else {
    // str[i] -= ans;
    // dfs(str, i + 1);
    // str[i] += ans;
    // }
    // }
    // }

    // //傻逼题目
    // private Set<TreeNode> list = new HashSet<>();
    // public List<TreeNode> generateTrees(int n) {
    // boolean[] flag = new boolean[n];
    // TreeNode root = new TreeNode(-1);
    // TreeNode cur = root;
    // TreeNode prev = root;
    // dfs(n, flag, 0, root);
    // for()
    // }
    //
    // private void dfs(int n, boolean[] flag, int index,
    // TreeNode root) {
    // if(index == n) {
    // list.add(root);
    // }
    // for(int i = 1; i <= n; i++) {
    // if(flag[i]) {
    // continue;
    // }
    // flag[i] = true;
    // if(root.val = -1) {
    // root.val = i;
    // } else {
    // builderNode(root, i);//添加结点
    // }
    // dfs(n, flag, index + 1, root);
    // deleteNode(root, i);//删除结点
    // }
    // }
    //
    // private void deleteNode(TreeNode root, int val) {
    // TreeNode cur = root;
    // TreeNode prev = cur;
    // if(root.val == val) {
    // root.val = -1;
    // }else {
    // while(cur.val != val) {
    // prev = cur;
    // if(cur.val > val) {
    // cur = cur.left;
    // } else {
    // cur = cur.right;
    // }
    // }
    // if(prev.val > val) {
    // prev.left = null;
    // } else {
    // prev.right = null;
    // }
    // }
    // }
    //
    // private void builderNode(TreeNode root, int val) {
    // TreeNode node = new TreeNode(val);
    // TreeNode cur = root;
    // TreeNode prev = cur;
    // while(cur != null) {
    // prev = cur;
    // if(cur.val > val) {//向左寻找
    // cur = cur.left;
    // } else {//向右寻找
    // cur = cur.right;
    // }
    // }
    // //cur == null
    // if(prev.val > val) {
    // prev.left = node;
    // } else {
    // prev.right = node;
    // }
    // }

    // // 6.统计各位数字都不同的数字个数(动态规划)
    // public int countNumbersWithUniqueDigits(int n) {
    //     if (n == 0) {
    //         return 1;
    //     }
    //     int[] dp = new int[n + 1];
    //     dp[0] = 1;
    //     dp[1] = 10;
    //     for (int i = 2; i <= n; i++) {
    //         dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - 2]) * (10 - i + 1);
    //     }
    //     return dp[n];
    // }

    // //7.格雷编码(回溯暴力超时)
    // private List<Integer> ret;
    // private List<Integer> list = new ArrayList<>();
    // public List<Integer> grayCode(int n) {
    //     int num = (int)Math.pow(2, n);
    //     boolean[] path = new boolean[num];
    //     path[0] = true;
    //     list.add(0);//每一位都会有
    //     dfs(num, path, 0);
    //     return list;
    // }

    // private void dfs(int num, boolean[] path, int key) {
    //     if(num == list.size() && isValue(list.get(num - 1), 0)) {
    //         ret = new ArrayList<>(list);
    //         return;
    //     }
    //     for(int i = 1; i < num; i++) {
    //         if(path[i]) {
    //             continue;
    //         }
    //         if(!isValue(list.get(list.size() - 1), i)) {
    //             continue;
    //         }
    //         path[i] = true;
    //         list.add(i);
    //         dfs(num, path, key);
    //         path[i] = false;
    //         list.remove(list.size() - 1);
    //     }
    // }

    // private boolean isValue(int a, int b) {
    //     int flag = a ^ b;
    //     int count = 0;
    //     while(flag > 0) {
    //         if((flag & 1) == 1) {
    //             count++;
    //         }
    //         flag >>= 1;
    //     }
    //     return count == 1;
    // }

    // //格雷码(格雷码原理)
    // public List<Integer> grayCode(int n) {
    //     List<Integer> list = new ArrayList<>();
    //     for(int i = 0; i < 1 << n; i++) {
    //         list.add(i ^ i >> 1);
    //     }
    //     return list;
    // }

//    //8.二进制手表(回溯)
//    private List<String> list = new ArrayList<>();
//    public List<String> readBinaryWatch(int turnedOn) {
//        int[] nums = {8,4,2,1,32,16,8,4,2,1};
//        dfs(turnedOn, nums, 0, 0, 0);
//        return list;
//    }
//
//    private void dfs(int turnedOn, int[] nums, int begin, int hour, int minute) {
//        //检验钟表合理性
//        if(hour > 11 || minute > 59) {
//            return;
//        }
//        //转化
//        if(turnedOn == 0) {
//            StringBuilder time = new StringBuilder();
//            time.append(hour + ":");
//            if(minute < 10) {
//                time.append(0);
//            }
//            time.append(minute);
//            list.add(time.toString());
//            return;
//        }
//        for(int i = begin; i < nums.length; i++) {
//            turnedOn--;
//            if(i < 4) {
//                hour += nums[i];
//            } else {
//                minute += nums[i];
//            }
//            dfs(turnedOn, nums, i + 1, hour, minute);
//            turnedOn++;
//            if(i < 4) {
//                hour -= nums[i];
//            } else {
//                minute -= nums[i];
//            }
//        }
//    }
////
//    //9.递增子序列(回溯)
//    private Set<List<Integer>> set = new HashSet<>();
//    private List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> findSubsequences(int[] nums) {
//        dfs(nums, 0);
//        List<List<Integer>> ret = new ArrayList<>();
//        for(List<Integer> list : set) {
//            ret.add(list);
//        }
//        return ret;
//    }
//
//    private void dfs(int[] nums, int begin) {
//        if(path.size() >= 2) {
//            set.add(new ArrayList<>(path));
//        }
//        for(int i = begin; i < nums.length; i++) {
//            if(!path.isEmpty() && path.get(path.size() - 1) > nums[i]) {
//                continue;
//            }
//            path.add(nums[i]);
//            dfs(nums, i + 1);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    //递增子序列(回溯 + 数组set优化)
//    private List<List<Integer>> ret = new ArrayList<>();
//    private List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> findSubsequences(int[] nums) {
//        dfs(nums, 0);
//        return ret;
//    }
//
//    private void dfs(int[] nums, int begin) {
//        if(path.size() >= 2) {
//            ret.add(new ArrayList<>(path));
//        }
//        int[] set = new int[201];
//        for(int i = begin; i < nums.length; i++) {
//            if(set[nums[i] + 100] == 1 ||
//                    (!path.isEmpty() && path.get(path.size() - 1) > nums[i])) {
//                continue;
//            }
//            set[nums[i] + 100] = 1;
//            path.add(nums[i]);
//            dfs(nums, i + 1);
//            path.remove(path.size() - 1);
//        }
//    }

    //10.黄金矿工(回溯)
    private int row;
    private int col;
    private int maxRet;
    private int max;
    public int getMaximumGold(int[][] grid) {
        this.row = grid.length;
        this.col = grid[0].length;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] != 0) {
                    max = 0;
                    boolean[][] path = new boolean[row][col];
                    dfs(grid, i, j, path);
                }
            }
        }
        return maxRet;
    }

    private void dfs(int[][] grid, int x, int y, boolean[][] path) {
        if(x < 0 || x >= row || y < 0 || y >= col ||
                path[x][y] || grid[x][y] == 0) {
            return;
        }
        path[x][y] = true;
        max += grid[x][y];
        if(max > maxRet) {
            maxRet = max;
        }
        dfs(grid, x - 1, y, path);
        dfs(grid, x + 1, y, path);
        dfs(grid, x, y - 1, path);
        dfs(grid, x, y + 1, path);
        path[x][y] = false;
        max -= grid[x][y];
    }
}

class Main {
    public static void main(String[] args) {
        int[][] arr = { {0, 6, 0}, { 5, 8, 7 }, { 0, 9, 0 }};
        Test test = new Test();
        test.getMaximumGold(arr);
    }
}
